package com.kabuda.zhugehot200;

import java.util.*;

/**
 * @author kabuda
 * @date 2025-03-24 22:13
 * @description
 */
public class t870_优势洗牌 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(advantageCount(new int[]{2, 7, 11, 15}, new int[]{1, 10, 4, 11})));
    }

    public static int[] advantageCount(int[] A, int[] B) {
        int[] sortedA = A.clone();
        Arrays.sort(sortedA);//找一个代价最小的去匹配B中的，比B大，在A中又是最小的
        int[] sortedB = B.clone();
        Arrays.sort(sortedB);//避免比较时，A每次都要重头遍历

        Map<Integer, Deque<Integer>> assigned = new HashMap();
        for (int b : B)
            assigned.put(b, new LinkedList());

        Deque<Integer> remaining = new LinkedList();

        int j = 0;
        for (int a : sortedA) {
            if (a > sortedB[j]) {
                assigned.get(sortedB[j++]).add(a);
            } else {
                remaining.add(a);
            }
        }

        int[] ans = new int[B.length];
        for (int i = 0; i < B.length; ++i) {
            if (assigned.get(B[i]).size() > 0)
                ans[i] = assigned.get(B[i]).removeLast();
            else
                ans[i] = remaining.removeLast();
        }
        return ans;
    }


}
